package practise.alogrithm.gotoSiliconValley.array;

/**
 * find out a min number from a rotated array, note this array contains the duplicated elements.
 * if the left element is less than mid AND right element not less than mid, then we can get the min
 * from left,
 * else if the mid equals to the left and right, shrunk the range from both left or right, and from one side also ok,
 * but it will take more elements for the calculation
 * else if find mid less than the left , then the min in the left, set right as min, loop again
 * else if find mid larger than the right, then the min in the right, set left as min, loop again,
 * until first if or left adjacent to right
 */
public class MinFromRotateArray {
    public int findMin(int[] array){
        int left=0,right=array.length,mid,min=array[left];
        while (left<right){
            mid=left+(right-left)/2;
            while (array[left]==array[mid]){
                left++;
            }
            while (array[right]==array[mid]){
                right--;
            }
            if(array[left]<array[mid]&&array[right]>array[mid]){
                return array[left];
            }
            if(array[left]>array[mid]){
                right=mid;
            }
            else{
                left=mid;
            }
        }
        return Math.min(array[left],array[right]);
    }
}
